perm filename MEMORY[0,BGB] blob
sn#073903 filedate 1973-11-29 generic text, type C, neo UTF8
COMMENT ā VALID 00007 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 4.0 MEMORY - DATA STRUCTURES.
C00003 00003 4.1 Introduction to Geometric Data Structures.
C00005 00004 Figure - THE WINGED EDGE.
C00012 00005 Winged Edge Data Structure.
C00017 00006 4.3 Representation of a Geometric Mental Universe.
C00020 00007 4.5 Interfacing to Other Data Types.
C00021 ENDMK
Cā;
4.0 MEMORY - DATA STRUCTURES.
4.1 Introduction to Geometric Data Structures.
4.2 The Winged Edge Polyhedron Representation.
4.3 Representation of a Geometric Mental Universe.
4.4 Two Image Representations: CRE and FEV.
4.5 Interfacing to Other Data Types.
4.1 Introduction to Geometric Data Structures.
In order to get a computer to deal with the physical world
it must have a data representation on which computations involving
space, time, shape, size and the appearance of things can be done.
In this chapter, an implemented
representation for the topology, geometry and
photometry of physical objects, images and for geometric mental universe
are explained.
The data structures
discussed are implemented as small blocks of words containing
pointers and data in the fashion usual to graphics and simulation;
an introduction to this technology can be found in Knuth; and
although the language of implementation is PDP-10 machine code, the
data and functions presented below are accessible from higher level
languages like LISP and ALGOL.
Figure - THE WINGED EDGE.
(As viewed from the exterior of a solid).
\ /
NCCW(E) \ / PCW(E)
\ /
\ /
\ /
ā PVT(E)
|
|
NFACE(E) E PFACE(E)
|
|
NVT(E) ā
/ \
/ \
/ \
NCW(E) / \ PCCW(E)
/ \
Winged Edge Data Structure.
Bodies, faces, edges and vertices are represented by blocks
of contiguously addressed words. A single block size of ten words is
adequate. A single word, like a LISP node, can hold two addresses or
a floating point number. The BFEV blocks are pointed at by the
address of their word numbered zero which contains control bits
indicating whether the block is a body, face, edge or vertex. Figure
2.1 illustrates the block format that is being presented as an
example of a winged edge data structure; a minimal number of words
for each block is indicated.
The basic geometric datum is the vertex locus, which is
stored in three words of each vertex block at positions -3, -2, -1;
these positions are named XWC, YWC, ZWC respectively; the letters
"WC" standing for "world coordinates".
The basic topological data are the three rings of the body;
(a ring of faces, a ring of edges, and a ring of vertices) and the
winged edge pointers (eight such pointers in each edge block,and one
such pointer in each face and vertex block). The face, edge and
vertex ring pointers are stored at positions +1, +2, +3; each
position has two names: NFACE, NED, NVT for the left pointers
respectively; and PFACE, PED, PVT for the right. A face, edge or
vertex can only belong to one body and so there is only one body node
in a given face, edge or vertex ring; and that body node serves as
the head of the ring. The reason for double pointer rings is for the
sake of rapid deletion; other minor advantages would not justify the
use of double rings.
The eight WINGED pointers of an edge block include: two
pointers to the faces of that edge, two pointers to the vertices of
that edge, and four pointers to the next edges clockwise and counter
clockwise in each of that edge's two faces; these last four pointers
are called the wings of that edge. As figure 2.2 suggests, four of
these eight pointers are stored in the same positions and referred to
by the same names as the face and vertex ring pointers; namely the
NFACE, PFACE, NVT and PVT pointers. There are four ways in which a
pair of faces and a pair of vertices can be placed into the two face
positions and two vertex positions of an edge; by constraining these
choices two bits are implicitly encoded, one bit is called the edge
parity, and the other is called the surface parity; these bits are
explained later. Finally, the single winged edge pointer found in
faces and vertices is kept in the position named PED and it points to
one of the edges belonging to that face or vertex.
Although the vertices in figure 2.2 are shown with three
edges, vertices may have any number of edges; those other potential
edges would not be directly connected to E and so were not shown.
4.3 Representation of a Geometric Mental Universe.
At the top of the data structure is a single universe node
from which everything else can be reached. Immediately below the
universe node is a ring of world models. A robot dealing with
physical world sensor input, such as video data, has one of its world
models dedicated to simulating the immediate here and now; this
mental world is called the reality world model. In addition to the
reality world, a robot may have fantasy world models for problem
solving, planning or for recalling platonic object prototypes. In the
following, a two world mental universe will be the most common, with
the reality world being referred to as a "map" and the fantasy world
being referred to as a "dictionary".
Geometric world models have four basic kinds of nodes:
body, face, edge and vertex. The face, edge and vertex nodes are used
to form polyhedrons which may be attached to body nodes. Body nodes
in turn are connected to each other in rings and trees to form a
world model. Additional kinds of nodes discribe cameras and light
sources as well as temporary data such as shadows, spines, and
trajectories.
The image data structure presented in this section is a
computer's internal notation for what is vulgarly called a line
drawing; the common term is misleading because it does not suggest
the equally important space between the lines; terms closer to the
idea would be "mosaic drawing" or "stained glass window drawing".
The data structure has main levels: TV raster, video
intensity contour, arc contour, and region-edge.
4.5 Interfacing to Other Data Types.